#include <iostream>
#include <vector>
using namespace std;

#define MAXN 100+5
#define INF 0x3F3F3F3F
int n;
int Edge[MAXN][MAXN];
int ShortRoute[MAXN];
int VSet[MAXN];
int AdjVex[MAXN];
int e;
int min_edges;
int min_cost;

struct EHistory {
	int s;
	int e;
	EHistory(int s, int e):s(s), e(e) { }
};

vector<EHistory> History;

void input() {
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=n; j++) {
			cin >> Edge[i][j];
			if (i==j) {
				Edge[i][j] = INF;
			}
			if (i!=j && Edge[i][j]==0) {
				e++;
			}
		}
	}
	e /= 2;
}

void prim() {
	for (int i=1; i<=n; i++) {
		ShortRoute[i] = Edge[1][i];
		AdjVex[i] = 1;
	}
	VSet[1] = 1;
	for (int i=2; i<=n; i++) {
		int min_c = INF;
		int min_v = -1;
		for (int j=1; j<=n; j++) {
			if (!VSet[j] && ShortRoute[j] < min_c) {
				min_c = ShortRoute[j];
				min_v = j;
			}
		}
		VSet[min_v] = 1;
		min_cost += Edge[AdjVex[min_v]][min_v];
		if (Edge[AdjVex[min_v]][min_v] > 0) {
			int a=AdjVex[min_v], b=min_v, t;
			if (a>b) {
				t=a; a=b; b=t;
			}
			History.push_back(EHistory(a, b));
			min_edges++;
		}
		for (int j=1; j<=n; j++) {
			if (Edge[min_v][j] < ShortRoute[j]) {
				ShortRoute[j] = Edge[min_v][j];
				AdjVex[j] = min_v;
			}
		}
	}
}

void print() {
	cout << min_edges << endl;
	for (int i=0; i<History.size(); i++) {
		cout << History[i].s << " " << History[i].e << endl;
	}
	cout << min_cost << endl;
}

int main() {
	cin >> n;
	input();
	prim();
	print();
	return 0;
}
